The well-known Internet network is a notoriously well-known publicly accessible communication network at the time of filing the present patent application, and arguably the most robust information and communication source ever made available. The Internet is used as a prime example in the present application of a data-packet-network which will benefit from the apparatus and methods taught in the present patent application, but is just one such network, following a particular standardized protocol. As is also very well known, the Internet (and related networks) are always a work in progress. That is, many researchers and developers are competing at all times to provide new and better apparatus and methods, including software, for enhancing the operation of such networks.
In general the most sought-after improvements in data packet networks are those that provide higher speed in routing (more packets per unit time) and better reliability and fidelity in messaging. What is generally needed are router apparatus and methods increasing the rates at which packets may be processed in a router.
As is well-known in the art, packet routers are computerized machines wherein data packets are received at any one or more of typically multiple ports, processed in some fashion, and sent out at the same or other ports of the router to continue on to downstream destinations. As an example of such computerized operations, keeping in mind that the Internet is a vast interconnected network of individual routers, individual routers have to keep track of which external routers to which they are connected by communication ports, and of which of alternate routes through the network are the best routes for incoming packets. Individual routers must also accomplish flow accounting, with a flow generally meaning a stream of packets with a common source and end destination. A general desire is that individual flows follow a common path. The skilled artisan will be aware of many such requirements for computerized processing.
Typically a router in the Internet network will have one or more Central Processing Units (CPUs) as dedicated microprocessors for accomplishing the many computing tasks required. In the current art at the time of the present application, these are single-streaming processors; that is, each processor is capable of processing a single stream of instructions. In some cases developers are applying multiprocessor technology to such routing operations. The present inventors have been involved for some time in development of dynamic multistreaming (DMS) processors, which processors are capable of simultaneously processing multiple instruction streams. One preferred application for such processors is in the processing of packets in packet networks like the Internet.
In a data-packet processor, a configurable queuing system for packet accounting during processing is known to the inventor and disclosure of same is referenced herein as Ser. No. 09/737,375 in the cross-reference section of this specification. The queuing and accounting system has a plurality of queues arranged in one or more clusters, an identification mechanism for creating a packet identifier for arriving packets, insertion logic for inserting packet identifiers into queues and for determining into which queue to insert a packet identifier, and selection logic for selecting packet identifiers from queues to initiate processing of identified packets, downloading of completed packets, or for re-queuing of the selected packet identifiers.
A portion of memory in the above-described system is called packet memory. The packet memory is the memory where data packets reside during processing before they can be downloaded by a packet management unit (PMU) to an output network interface (ONI). During processing packet data may be altered. A portion of the packet memory is termed the local packet memory (LPM), and directly managed by hardware in the PMU instead of by software.
Whenever a data packet has been processed and is ready to be downloaded from memory, the processing core or streaming processor unit (SPU) sends a command (PKTDONE) to the PMU. This command contains, among other information, a packet identifier (typically a number) of the packet that is ready to be downloaded. The PMU will then proceed with the download of this packet if it resides in LPM. If not, SPU software operating through a system interface unit (SIU) will download the packet upon request from an external portion of packet memory (EPM).
Data packet processing requires loading of contexts with pertinent information to control the processing, and in a system known to the inventor, processing is accomplished by a Dynamic Multistreaming Processor running, in one embodiment, 8 streams. In this system there are at least eight contexts for processing data packets, and in some cases one or more redundant contexts allowing background loading.
The contexts are located physically within the streaming processor unit (SPU) core, which also has associated functional units required for processing. In a preferred embodiment each context can have a state of either PMU-owned or SPU-owned. When information is being preloaded into a context it is considered PMU-owned. When a stream is running with a context, the context is considered SPU-owned.
A context-selection mechanism is known to the inventor and is provided within PMU hardware in the processor, operating as part of or in conjunction with a register transfer unit (RTU), and the context-selection mechanism is adapted for selecting a best context from a pool of available contexts for processing a data packet. The context selection mechanism comprises an interface for communicating with other elements of a multi-streaming processor; circuitry for computing input data into a result value according to logic rule and for selecting a context based on the computed value, and a loading mechanism for preloading packet information for the selected packet into the selected context for subsequent processing.
The computation of the input data functions to enable identification and selection of a best context for processing a data packet according to the logic rule at the instant time such that a large number of context selections over a period of time acts to balance load pressure on functional units associated with stream clusters.
There is a possibility during operation that all of the contexts of a processor could be PMU-owned at any given time. Moreover some of the contexts may be undergoing pre-load operations while others are sitting idle waiting for PMU selection, preload, and release (activation). In this situation none of the contexts are available for processing because none are SPU-owned.
The lack of any contexts available for processing also means that no processing may occur involving servicing of any pending interrupts that may have been generated while all of the contexts are PMU-owned. It is noted herein that an interrupt may be PMU or SPU generated. In the case of all contexts being PMU-owned when there are one or more interrupts pending, then the SPU must wait until the PMU releases (activates) a context. This presents a problem in that it may take a long time to start executing an interrupt service routine for an interrupt. The problem is magnified if the interrupt that has been generated is due to a high priority event that needs immediate processing.
Therefore what is clearly needed is a mechanism for limiting the possibility of PMU ownership of all contexts to a very limited span of time. A mechanism such as this would insure a relatively small latency in response time for processing a potentially critical interrupt routine or routines that may be pending.